Networking protocols are used to facilitate the communication of data between computer systems and devices. A protocol determines such communication parameters and characteristics as the type of error checking to be used, any data compression methods, how a sending device indicates that it has finished sending data, and how a receiving device indicates that it has received data.
The availability of an accurate and fine-grained timer service is crucial to the efficient implementation of many networking protocols. Timers are used to determine when “timeouts” occur, i.e., when a timer expires, indicating that a predetermined amount of time has passed and that therefore an action or computer functions should be performed. For example, a response timeout occurs when no response from a sought device is received over the network within a predetermined amount of time after sending a request. The occurrence of a timeout can indicate to a device that it should stop waiting for a response, retransmit data, sever a connection to another device on the network, or perform one or more other functions.
Typically in a networking system, each connection of a reliable network protocol maintains several active timers to keep track of different timeouts supported by the protocol. In such protocols, multiple timers are maintained for each particular network connection to control the state of the connection based on predetermined conditions. For example, in the Transmission Control Protocol (TCP), one timer can be a retransmission timer that keeps track of the time elapsed after a request or data is transmitted to a connected device and before an acknowledgement is received from the connected device, so that the sending device can retransmit information if a timeout occurs. An idle timer can keep track of the time since any data frame or signal was last received on a particular connection, such that if an idle or “stale” timeout occurs, the connection can be shut down due to lack of activity. A keepalive timer can be started after an idle timeout occurs to keep track of the time elapsed since sending a test signal to test if the other computer system is still functioning and connected, so that if a timeout occurs before any response is received, the other computer system is considered non-functioning or non-communicative. An acknowledgement delay timer can count down a predetermined duration of time after receiving a packet of data, thereby causing a delay for acknowledging the reception of the packet so that a single acknowledgement can be later sent (when the timeout occurs) after receiving multiple close-together packets, thus promoting a reduction in the amount of unnecessary acknowledgments. All these timers can be maintained for each network connection. For example, networking functions like server load balancing and layer-4 protocol termination require such multiple timers to be maintained per connection of the subject device to another device over the network.
Setting, resetting, and expiration of these timers is typically supported and maintained by a system timer task or service. In many conventional systems, a counter is maintained for each connection timer associated with each connection, the counters being stored in a memory control block associated with each connection in a connection table. The timer task periodically (e.g., every 500 milliseconds) examines the entries of the entire connection table and decrements all the counters for the active connections. A timeout is declared when the value of a counter becomes zero. This method requires several memory-related accesses per connection, such as acquiring a lock to the connection control block so that other tasks may not access the block, a read of the counter value, write to decrement the counter value, and an unlock operation to free the control block for other tasks.
In many implementations of a networking system, a single device can have many different network connections to other devices or systems. Systems implementing networking functions such as server load balancing normally support a large number of connections (e.g., on the order of 100,000 ) and require high throughput. When there are a large amount of active connections with more than one pending timer, a large amount of timer entries must be maintained by the system timer service. Since the examination of the entire connection table for timeouts, and the setting and resetting of timers, are very extensive and frequent protocol operations, maintaining a large amount of active timer entries tends to limit the overall system performance. Typical timer service implementations tend not to scale, and thus become the limiting factor of the protocol stack performance. Multiple memory-related accesses across a large number of connections can result in overall performance degradation and a bottleneck; for example, the packet forwarding code may try to access the connection table (control block) while the timer task has acquired a lock on the connection table while writing or examining timer values.
Accordingly, what is needed is a system and method for more efficiently maintaining timers in networking systems having many connections. The present invention addresses such a need.